package gold.gold03;

import java.util.*;

/**
 * 字符串, 排列组合,
 * 注意字符串的char是无重复的, 可以用set之类的。
 * 注意List的方法是.size(), String是.length(), Arrays是.length。
 */
public class S0807无重复字符串的排列组合 {

    /**
     * 77, 看一眼别人的方法, 尽力了, 试一下交换, 交换目的感觉并不是交换, 而是让每一个没有被选中的值在第i个位置出现。
     * 比如第一位确定, 然后把后面每一位和第二位交换, 得到的就是每一个char在第二位出现的样子。
     * 这样通过swap的方式实现遍历, 可以保证前面已经选中过的点不会再被选中。
     */
    private int insertPosi = 0;
    public String[] permutation3(String S) {
        if(S == null || S.length() == 0) return new String[]{""};
        char[] charArray = S.toCharArray();
        int resultLength = 1;
        for(int i = 2; i <= S.length(); i++) resultLength *= i;

        String[] resultStringArray = new String[resultLength];
        insertString(resultStringArray, charArray, 0);
        return resultStringArray;
    }

    /**
     * 99, 替换成新的insertString之后, 从778变成99, 两者的考虑方式有本质的不同,
     * insertString2是每swap一次, 就创建了一种新的排列方式, 所以每次swap之后, 都要进行判断, 然后插入新的值
     * insertString1是每swap一次, 确定了一个位置的值, 也就是说, 同一个位置swap也是可以的/必须的, 因为那也是一个选项。
     * 在2中同位置的swap, 没有创建新的排列方式, 比如abcd, a和a swap得到了abcd, b和b swap也得到了abcd, 这个重复情况的判断比较麻烦。
     * 但是1方法中, 同位置的swap就ok的。
     */
    private void insertString(String[] resultStringArray, char[] charArray, int iterPosi){
        if(iterPosi == charArray.length - 1) resultStringArray[insertPosi++] = new String(charArray);
        for(int i = iterPosi; i < charArray.length; i++){
            swapCharArray(charArray, iterPosi, i);
            insertString(resultStringArray, charArray, iterPosi + 1);
            swapCharArray(charArray, iterPosi, i);
        }
    }
    private void insertString2(String[] resultStringArray, char[] charArray, int iterPosi){
        for(int i = iterPosi; i < charArray.length; i++){
            swapCharArray(charArray, iterPosi, i);
            String tempString = new String(charArray);
            // 这个交换的时候会忽略一些情况, 难以解决, 这样只是权宜之计。
            if(insertPosi < resultStringArray.length &&
                    !tempString.equals(insertPosi > 0? resultStringArray[insertPosi - 1]: ""))
                resultStringArray[insertPosi++] = new String(charArray);
            insertString(resultStringArray, charArray, iterPosi + 1);
            swapCharArray(charArray, iterPosi, i);
        }
    }

    private void swapCharArray(char[] charArray, int loc1, int loc2){
        char temp1 = charArray[loc1];
        charArray[loc1] = charArray[loc2];
        charArray[loc2] = temp1;
    }

    /**
     * 100, 别人的方法。上面的1和这个一样。
     */
    int I=0;//返回数组的索引
    public String[] permutation2(String S) {
        int N=getlen(S.length());
        char[] c=S.toCharArray();
        String[] res=new String[N];
        backtrack(0,c,res);
        return res;
    }
    int getlen(int n){//n:1-9
        if(n==1) return 1;
        return n*getlen(n-1);
    }
    void backtrack(int index,char[] c,String[] res){
        if(index==c.length-1){
            res[I++]=String.valueOf(c);
            return;
        }
        for(int i=index;i<c.length;i++){//选择路径列表
            swap(index,i,c);//做出选择
            backtrack(index+1,c,res);//继续DFS决策树
            swap(index,i,c);//撤销选择
        }
    }
    void swap(int i,int j,char[] c){
        char t=c[i];
        c[i]=c[j];
        c[j]=t;
    }


    /**
     * 5, 先a, 然后在a的每一种位置都插入b得到ab, ba, 然后在ab/ ba各自的每一个位置上插入c, 这样迭代。
     * 感觉时间慢是因为StringBuilder操作, 改成char会小很多?复杂度其实就这样。
     */
    public String[] permutation(String S) {
        if(S == null || S.length() == 0) return new String[]{""};
        // List<String> resultList = new ArrayList<>();
        // List<String> resultList2 = new ArrayList<>(); // 迭代修改有麻烦
        List<String> resultList = new LinkedList<>();
        List<String> resultList2 = new LinkedList<>(); // 换成LinkedList可以通过, ArrayList超时。
        resultList.add("");
        StringBuilder sb = new StringBuilder();
        for(char c: S.toCharArray()){
            for(String s: resultList){
                sb.delete(0, sb.length());
                sb.append(s);
                for(int i = 0; i <= s.length(); i++){
                    sb.insert(i, c);
                    resultList2.add(sb.toString());
                    sb.delete(i, i+1);
                }
            }
            // 把第二个List的内容腾到第一个里面
            resultList.removeAll(resultList);
            resultList.addAll(resultList2);
            resultList2.removeAll(resultList2);
        }
        String[] resultArray = new String[resultList.size()];
        for(int i = 0; i < resultArray.length; i++){
            resultArray[i] = resultList.get(i);
        }
        return resultArray;

    }



    public String[] permutationFail(String S) {
        if(S == null || S.length() == 0) return null;
        Set<Character> charSet = new HashSet<>();
        for(char c: S.toCharArray()){
            charSet.add(c);
        }
        List<String> resultList = new ArrayList<>();
        // String的拼接效率很低, 可以试试别的。
        resultList.add("");
        for(int i = 0; i < S.length(); i++){
            List<String> newResultList = new ArrayList<>();// 小心迭代修改会出错
            for(String curString : resultList){

            }
        }
        return null;
    }


}
